// dfs 回溯

// DFS 解析：
// 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
// 终止条件：
// 返回 false：
// 行或列索引越界
// 当前矩阵元素与目标字符不同
// 当前矩阵元素已访问过（通过将访问过的字符置空）
// 返回 true： k = word.length - 1 ，即字符串 word 已全部匹配。
// 递推过程：
// 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。
// 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
// 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。
// 返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

let board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
  ],
  word = "ABCCED";

const exist = (board, word) => {
  const [m, n] = [board.length, board[0].length];

  const dfs = (i, j, index) => {
    // 越界、或者字符不匹配
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[index])
      return false;
    // 索引等于单词长度-1，说明全匹配上了
    if (index === word.length - 1) return true;
    // 保存当前字符
    const temp = board[i][j];
    // 将当前字符设置为空，防止四个方向dfs再次遍历到
    board[i][j] = "";
    // 四个方向遍历
    const res =
      dfs(i + 1, j, index + 1) ||
      dfs(i, j + 1, index + 1) ||
      dfs(i - 1, j, index + 1) ||
      dfs(i, j - 1, index + 1);
    // 恢复当前字符
    board[i][j] = temp;
    return res;
  };

  // 从第一个匹配的字符处开始dfs
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, 0)) return true;
    }
  }

  return false;
};
